#include <iostream>
#include <string.h>
#include <vector>
using namespace std;


struct cpny{
	int p=-1;
	vector<int> v;
	void cmp(cpny x,int num){
		if(p <= x.p){
			p = x.p;
			v = x.v;
			v.push_back(num);
		}
		return;
	}
	cpny operator + (int x){
		cpny ans;
		ans.p = x+(p==-1?0:p);
		ans.v = v;
		return ans;
	}
};


int main(){
	int n,m;
	cin>>n>>m;
	int a[n+1][m+1];
	cpny dp[n+1][m+1];
//	memset(dp,0,sizeof(dp));
	memset(a,0,sizeof(a));
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>a[i][j];
	for(int i=1;i<=n;i++){
		for(int j=0;j<=m;j++){
			for(int sum=0;sum<=j;sum++){
				dp[i][j].cmp((dp[i-1][j-sum]+a[i][sum]),sum);
			}
//			cout<<dp[i][j].p<<" ";
		}
//		cout<<endl;
	}
	cout<<dp[n][m].p<<endl;
	for(int i=0;i<n;i++)
		cout<<i+1<<" "<<dp[n][m].v[i]<<endl;
	return 0;
}
